//================v1要点总结===============
/**
 * 1.BFS 尝试, 遍历可达性，并进行count统计 + 最长路径统计
 * 2.当没有新鲜橘子，或者没有坏橘子时，需要考虑
 * 
 */


/**
 * @param {number[][]} grid
 * @return {number}
 */
var orangesRotting = function (grid) {
    let r = grid.length
    let c = grid[0].length
    let tempArr = new Array(r)
    let dir = [[-1, 0], [0, 1], [1, 0], [0, -1]]
    let hasBad = false
    let hasNew = false
    let restCount = r * c
    // 开始广度遍历
    let queue = []
    for (let i = 0; i < r; i++) {
        let tempCArr = new Array(c)
        for (let j = 0; j < c; j++) {
            //先找是否存在四面都是 0 或边界的，右的话直接返回 -1
            if (grid[i][j] === 0) {
                tempCArr[j] = 0
                restCount--
                continue
            }
            tempCArr[j] = grid[i][j] === 1 ? 300 : grid[i][j]

            if (tempCArr[j] === 2) {
                queue.push([i, j])
                restCount--
                //烂橘子就不用判断了
                if (!hasBad) {
                    hasBad = true
                }
                continue
            }

            if (!hasNew) {
                hasNew = true
            }

            let count = 4
            for (let k = 0; k < dir.length; k++) {
                let tempR = i + dir[k][0]
                let tempC = j + dir[k][1]
                if (tempR < 0 || tempC < 0 || tempR >= r || tempC >= c || grid[tempR][tempC] === 0) {
                    count--
                }
            }
            if (count === 0) {
                return -1
            }
        }
        tempArr[i] = tempCArr
    }

    // 如果连烂橘子都没有，直接返回
    if (!hasBad) {
        if (!hasNew) {
            return 0
        } else {
            return -1
        }
    }

    // 开始广度优先遍历
    let rslt = 2
    while (queue.length) {
        let temp = queue.shift()
        let [x, y] = temp
        let lastVal = tempArr[x][y]
        for (let i = 0; i < dir.length; i++) {
            let tempR = x + dir[i][0]
            let tempC = y + dir[i][1]
            if (tempR >= 0 && tempR < r && tempC >= 0 && tempC < c && tempArr[tempR][tempC] !== 0 && tempArr[tempR][tempC] === 300) {
                tempArr[tempR][tempC] = Math.min(tempArr[tempR][tempC], lastVal + 1)
                rslt = Math.max(rslt, tempArr[tempR][tempC])
                queue.push([tempR, tempC])
                restCount--
            }
        }
    }
    if (restCount > 0) {
        return -1
    }
    return rslt - 2
};

// console.log(orangesRotting([[2, 1, 1], [1, 1, 0], [0, 1, 1]]))
console.log(orangesRotting([
    [2],
    [2],
    [1],
    [0],
    [1],
    [1]]))
// console.log(orangesRotting([
//     [2, 0, 1, 1, 1, 1, 1, 1, 1, 1],
//     [1, 0, 1, 0, 0, 0, 0, 0, 0, 1],
//     [1, 0, 1, 0, 1, 1, 1, 1, 0, 1],
//     [1, 0, 1, 0, 1, 0, 0, 1, 0, 1],
//     [1, 0, 1, 0, 1, 0, 0, 1, 0, 1],
//     [1, 0, 1, 0, 1, 1, 0, 1, 0, 1],
//     [1, 0, 1, 0, 0, 0, 0, 1, 0, 1],
//     [1, 0, 1, 1, 1, 1, 1, 1, 0, 1],
//     [1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
//     [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]))